package dataStructure.dynamic;

import java.util.Arrays;

/**
 * @author lhn
 * @date 2024-09-10 13:54
 */

public class KnapsackProblem {
    public static void main(String[] args) {
        int[] weight = {1, 4, 3};   // 物品重量
        int[] value = {1500, 3000, 2000};   // 物品价值
        int maxWeight = 4;  // 背包最大重量

        int[][] v = new int[weight.length + 1][maxWeight + 1];
        int[][] path = new int[weight.length + 1][maxWeight + 1];;
        // i 是物品索引（从0开始），j 是背包重量
        for (int i = 0; i <= weight.length; i++) {
            for (int j = 0; j <= maxWeight; j++) {
                if (i == 0 || j == 0) {
                    v[i][j] = 0;    // 初始化第一行和第一列
                } else if (j < weight[i - 1]) {
                    v[i][j] = v[i - 1][j];  // 当前背包容量小于物品重量，无法装入物品
                } else {
                    // 背包容量大于物品重量，选择装入物品或者不装入物品，取最大价值
//                    v[i][j] = Math.max(v[i - 1][j], value[i-1] + v[i - 1][j - weight[i-1]]);

                    // 使用path记录装入物品
                    if (v[i - 1][j] < value[i - 1] + v[i - 1][j - weight[i - 1]]) {
                        // 装入当前物品
                        v[i][j] = value[i - 1] + v[i - 1][j - weight[i - 1]];
                        path[i][j] = 1; // 记录装入物品
                    } else {
                        // 不装入当前物品
                        v[i][j] = v[i - 1][j];
                        path[i][j] = 0;
                    }
                }
            }
        }

        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[0].length; j++) {
                System.out.print(v[i][j] + " ");
            }
            System.out.println();
        }

        // 获取最大价值
        int maxValue = v[weight.length][maxWeight];
        System.out.println("最大价值为: " + maxValue);

        for (int i = 0; i < path.length; i++) {
            for (int j = 0; j < path[0].length; j++) {
                System.out.print(path[i][j] + " ");
            }
            System.out.println();
        }

        // 从最后一个物品和最大容量开始回溯
        int i = path.length - 1;
        int j = path[0].length - 1;
        while (i > 0 && j > 0) {
            if (path[i][j] == 1) {
                // path[i][j] == 1 表示在第i个物品可选的情况下，当背包容量为j时，选择了该物品
                System.out.println("第" + i + "个物品被选中" + i + " " + j);
                j -= weight[i - 1]; // 更新背包容量，减去当前物品重量 如i=3 j=4，减去weight[2]后 j=1空间
            }
            i--;
        }
    }
}
